package com.lw.leetcode.arr.b;

/**
 * Created with IntelliJ IDEA.
 * 6106. 统计无向图中无法互相到达点对数
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/26 19:03
 */
public class CountPairs {

    public static void main(String[] args) {
        CountPairs test = new CountPairs();

        // 0
        int[][] arr = {{0, 1}, {0, 2}, {1, 2}};
        int k = 3;

        // 14
//        int[][] arr = {{0, 2}, {0, 5}, {2, 4}, {1, 6}, {5, 4}};
//        int k = 7;

        // 14
//        int[][] arr = {};
//        int k = 100000;

        long l = test.countPairs(k, arr);
        System.out.println(l);
    }

    private int[] arr;

    public long countPairs(int n, int[][] edges) {
        arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = i;
        }
        for (int[] edge : edges) {
            int a = find(edge[0]);
            int b = find(edge[1]);
            if (a != b) {
                arr[b] = a;
            }
        }
        long[] counts = new long[n];
        long[] sums = new long[n];
        for (int i = 0; i < n; i++) {
            counts[find(i)]++;
        }
        sums[0] = counts[0];
        for (int i = 1; i < n; i++) {
            sums[i] = sums[i - 1] + counts[i];
        }
        long sum = 0;
        for (int i = 0; i < n; i++) {
            sum += (sums[i] - counts[i]) * counts[i];
        }
        return sum;
    }

    private int find(int v) {
        if (arr[v] == v) {
            return v;
        }
        arr[v] = find(arr[v]);
        return arr[v];
    }

}
